Recently, metric learning and similarity learning have attracted a large
amount of interest. Many models and optimisation algorithms have been proposed.
However, there is relatively little work on the generalization analysis of such
methods. In this paper, we derive novel generalization bounds of metric and
similarity learning. In particular, we first show that the generalization
analysis reduces to the estimation of the Rademacher average over
"sums-of-i.i.d." sample-blocks related to the specific matrix norm. Then, we
derive generalization bounds for metric/similarity learning with different
matrix-norm regularisers by estimating their specific Rademacher complexities.
Our analysis indicates that sparse metric/similarity learning with $L^1$-norm
regularisation could lead to significantly better bounds than those with
Frobenius-norm regularisation. Our novel generalization analysis develops and
refines the techniques of U-statistics and Rademacher complexity analysis.

本文利用 U 统计和 Rademacher 复杂性分析方法，针对度量学习和相似度学习，推导出了一种新的泛化边界方法，证明了 L1 范数正则化的稀疏度量学习和相似度学习可能比 Frobenius 范数正则化的模型具有更好的边界效果。